package com.zklh.leetcode.tree.middle;

import com.zklh.leetcode.tree.model.TreeNode;

/**
 * @author ：tong nan
 * @date ：Created in 2021/4/21 18:25
 * @description ：展开树
 * @modifiedBy ：
 */
public class FlattenTree {

    public void flatten(TreeNode root) {
        flattenTree(root);
    }

    /**
     * 展开树, 返回
     * @param node
     * @return
     */
    public TreeNode flattenTree(TreeNode node) {

        if (node == null) {
            return null;
        }
        TreeNode tempLeft = node.left, tempRight = node.right;
        TreeNode last = node;
        if (node.left != null) {
            last = flattenTree(node.left);
            node.left = null;
            node.right = tempLeft;
            last.right = tempRight;
        }
        if (node.right != null) {
            last = flattenTree(tempRight);
        }

        return last;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(6);
        FlattenTree flattenTree = new FlattenTree();
        flattenTree.flatten(root);
        System.out.println(111);
    }

}
